Search for: All records

Abstract For polyhedral constrained optimization problems and a feasible point$$\textbf{x}$$ $x$, it is shown that the projection of the negative gradient on the tangent cone, denoted$$\nabla _\varOmega f(\textbf{x})$$ ${\nabla }_{\Omega }f\left(x\right)$, has an orthogonal decomposition of the form$$\varvec{\beta }(\textbf{x}) + \varvec{\varphi }(\textbf{x})$$ $\beta \left(x\right)+\phi \left(x\right)$. At a stationary point,$$\nabla _\varOmega f(\textbf{x}) = \textbf{0}$$ ${\nabla }_{\Omega }f\left(x\right)=0$so$$\Vert \nabla _\varOmega f(\textbf{x})\Vert $$ $\Vert {\nabla }_{\Omega }f\left(x\right)\Vert$reflects the distance to a stationary point. Away from a stationary point,$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert$measure different aspects of optimality since$$\varvec{\beta }(\textbf{x})$$ $\beta \left(x\right)$only vanishes when the KKT multipliers at$$\textbf{x}$$ $x$have the correct sign, while$$\varvec{\varphi }(\textbf{x})$$ $\phi \left(x\right)$only vanishes when$$\textbf{x}$$ $x$is a stationary point in the active manifold. As an application of the theory, an active set algorithm is developed for convex quadratic programs which adapts the flow of the algorithm based on a comparison between$$\Vert \varvec{\beta }(\textbf{x})\Vert $$ $\Vert \beta \left(x\right)\Vert$and$$\Vert \varvec{\varphi }(\textbf{x})\Vert $$ $\Vert \phi \left(x\right)\Vert$.